1. Field of the Invention
The present invention relates to redundancy removal and in particular to a multi-mode redundancy removal, which quickly yields optimized results.
2. Related Art
An initial register transfer level (RTL) design for an integrated circuit often has nets and/or logic gates that are redundant. Note that a redundant net can be replaced by a constant or eliminated, whereas a redundant logic gate (logic) can be eliminated. As an example, FIG. 1A illustrates a simple circuit 100 including an AND gate 101 and an OR gate 102. AND gate 101 is coupled to two nets A and B, whereas OR gate 102 is coupled to a net C, which is an output of AND gate 101, and also to the net B. The output of OR gate 102 is coupled to a net D. Note that when signals on nets A and B are equal to one (A=B=1), then C=1. In this case, B=D=1. If A=0 and/or B=0, then C=0. In this case, D=B. Therefore, net C can be characterized as having a stuck-at-0 fault, i.e. C=0.
Because of this fault, an equivalent circuit to that shown in FIG. 1A can be formed by disconnecting net C from OR gate 102 (FIG. 1B) and instead connecting one input of OR gate 102 to ground (FIG. 1C). Using circuit simplification, both AND gate 101 and OR gate 102 can be replaced by a net 103 (FIG. 1D) connecting B and D, i.e. AB+B=B. Therefore, net A, AND gate 101, and OR gate 102 are “redundant” and can be eliminated from the design. Redundancy removal is a term of art referring to the technique that removes redundant logic (in the form of nets or logic gates) from a design.
Notably, even when the initial design has no redundancies, mapping and logic manipulations can introduce logic redundancy. Therefore, redundancy removal optimizations are typically invoked at multiple stages of the design optimization flow. Indeed, identifying and eliminating redundant nets/logic is an essential optimization strategy for decreasing design area, reducing critical path delay, and simplifying circuit testability analysis.
Redundancy removal techniques have been developed in both academia and industry. These techniques generally attempt to identify redundant logic by determining which nets are detectable with a particular input vector. This determination can be done through logic simulation, and then for nets that are still not detected, by a proof engine. As used herein, the proof engine refers to a software tool that can generate patterns to test a design. Exemplary well-known algorithms used by the proof engine can include the D Algorithm, PODEM (path-oriented decision making), or FAN (fan-out oriented). These techniques also generally attempt to improve the search heuristics that affect the performance of the proof engine.
Redundancy reduction is particularly susceptible to increasing design complexity. That is, performing redundancy removal for each net in a complex design can require significant time to analyze. Therefore, performing redundancy removal for complex designs can result in runtime explosion. To mitigate this risk, certain abort precautions can be added. Specifically, when redundancy reduction takes too long, the proof engine can abort its analysis.
To avoid calling the proof engine, some techniques perform dynamic simulation. In this technique, the proof engine attempts to derive a simulation vector that can be applied to the nets in fan-in/fan-out cones of the design with the anticipation that some of those nets are not redundant. Unfortunately, simulation typically entails worst-case quadratic performance because vector simulation requires traversal through the entire set of fan-in/fan-out cones of the design. Additionally, the simulation vector may fail to prove that a net is not redundant.
Other techniques attempt to improve redundancy reduction by partitioning the design or creating logic windows around the net to determine whether that net is redundant. Unfortunately, both partitioning and creating logic windows can result in unacceptable optimization (i.e. quality of result (QoR)) loss.
Therefore, a need arises for an improved redundancy reduction that eliminates the potential of runtime explosion while ensuring acceptable optimization.